//题目：
// 给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
// 输入为 非空 字符串且只包含数字 1 和 0。
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;
//代码:
class Solution 
{
public:
    string addBinary(string a, string b) 
    {
        // string ret;
        // reverse(a.begin(),a.end());
        // reverse(b.begin(),b.end());
        // int max_size=a.size()>b.size()?a.size():b.size();
        // int carry=0,result=0;//进位符和结果
        // for(int i=0;i<max_size;i++)
        // {
        //     if(i>=a.size())
        //     {
        //         result=carry+b[i]-'0';
        //         carry=result/2;
        //         result%=2;
        //     }
        //     else if(i>=b.size())
        //     {
        //         result=carry+a[i]-'0';
        //         carry=result/2;
        //         result%=2;
        //     }
        //     else 
        //     {
        //         result=carry+a[i]-'0'+b[i]-'0';
        //         carry=result/2;
        //         result%=2;
        //     }
        //     ret+=result+'0';
        // }
        // if(carry)ret+='1';
        // reverse(ret.begin(),ret.end());
        // return ret;

        //优雅解法
        string ret;
        int cur1=a.size()-1,cur2=b.size()-1,result=0;
        while(cur1>=0 || cur2>=0 || result)
        {
            if(cur1>=0)result+=a[cur1--]-'0';
            if(cur2>=0)result+=b[cur2--]-'0';
            ret+=result%2+'0';
            result/=2;
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }
};